package com.c2b.algorithm.leetcode.base;

import java.util.HashMap;
import java.util.Map;

/**
 * <a href='https://leetcode.cn/problems/max-pair-sum-in-an-array/'>数组中的最大数对和(Max Pair Sum in an Array)</a>
 * <p>给你一个下标从 0 开始的整数数组 nums 。请你从 nums 中找出和 最大 的一对数，且这两个数数位上最大的数字相等。</p>
 * <p>返回最大和，如果不存在满足题意的数字对，返回 -1 。</p>
 *
 * <p>
 * <b>示例</b>
 * <pre>
 * 示例 1：
 *      输入：nums = [51,71,17,24,42]
 *      输出：88
 *      解释：
 *          i = 1 和 j = 2 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 71 + 17 = 88 。
 *          i = 3 和 j = 4 ，nums[i] 和 nums[j] 数位上最大的数字相等，且这一对的总和 24 + 42 = 66 。
 *          可以证明不存在其他数对满足数位上最大的数字相等，所以答案是 88 。
 *
 * 示例 2：
 *      输入：nums = [1,2,3,4]
 *      输出：-1
 *      解释：不存在数对满足数位上最大的数字相等。
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *  <ul>
 *      <li>2 <= nums.length <= 100</li>
 *      <li>1 <= nums[i] <= 10^4</li>
 *  </ul>
 * </p>
 *
 * @author c2b
 * @since 2024/1/23 10:33
 */
public class LC2815MaxPairSumInArray_S {

    static class Solution {

        public int maxSum(int[] nums) {
            int res = -1;
            // 下标代表最大数位，下标值为最大数位对应的值
            int[] maxValues = new int[10];
            for (int num : nums) {
                int maxDigit = getMaxDigit(num);
                if (maxValues[maxDigit] != 0) {
                    res = Math.max(res, maxValues[maxDigit] + num);
                }
                maxValues[maxDigit] = Math.max(maxValues[maxDigit], num);
            }
            return res;
        }

        public int maxSum2(int[] nums) {
            int res = -1;
            // key：数字的最大数位；value：最大数位对应的最大数字
            Map<Integer, Integer> map = new HashMap<>();
            for (int num : nums) {
                int maxDigit = getMaxDigit(num);
                if (map.containsKey(maxDigit)) {
                    res = Math.max(res, map.get(maxDigit) + num);
                }
                // 更新 map对应key的value值
                map.put(maxDigit, Math.max(map.getOrDefault(maxDigit, 0), num));
            }
            return res;
        }

        private int getMaxDigit(int num) {
            int maxDigit = 0;
            while (num != 0) {
                maxDigit = Math.max(maxDigit, num % 10);
                num /= 10;
            }
            return maxDigit;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.maxSum(new int[]{51, 71, 17, 24, 42}));
        System.out.println(solution.maxSum(new int[]{1,2,3,4}));
        System.out.println(solution.maxSum(new int[]{31, 25, 72, 79, 74}));
    }
}
